<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>哈希表的实现</title>
</head>
<body>
    <script>
        // 哈希表一般是四维数组
        /*
        * 一维数组就是哈希表数组 []
        * 二维数组就是对应的每个坑位  如:哈希表数组有10个位置   [[],[],[]...]
        * 三维数组就是当求余得到的数存在的位置 当求与得到的数相同时二维数组就会包含多个三位数组 如:2 12 32 通过求余(value/二维数组的个数)计算(2/10,12/10,32/10)都要存到数组的第二个位置(一维数组包裹的10个二维数组的第2个) 
        * 四位数组就是三位维数组里的用于存放 key 和value 的地方 三维数组一般只有两个四维数组分别存储key和value 如: [ [ [[key],[value]] ,[[key],[value]] ] , [[[key],[value]],[[key],[value]]] ] 
        * [ [[key],[value]], [[key],[value]],  [[key],[value]] ]
        */

        // 封装哈希表的类
        function HashTable (){
            // 属性
            this.storage = [] // 用于存元素的数组
            this.count = 0  // 记录数组中已经存入了多少个元素
            this.limit = 7 // 数组的总长度
            // 方法 

            /*
            * 设计哈希函数
            * 把字符串转换成较大的数字:hashcode
            * 将大的数字hashcode压缩到数组的范围之内
            * @prames str 要转化的字符串 max 数组的最大范围 
            */
            HashTable.prototype.hashFunc = function (str,size){
                // 初始化hashcode的值
                var hashcode = 0
                // 霍纳法则,来计算hashcode的值
                for (let index = 0; index < str.length; index++) {
                    // 随意自定义一个质数(37)用于计算防止重复
                    // charCodeAt方法是通过字符串自带的属性获取每个字的Unicode编码
                    hashcode = 37 * hashcode + str.charCodeAt(index)
                }
                // 取余操作
               var  index = hashcode % size
               return index
            }
 
            // 插入和修改
            HashTable.prototype.put = function (key,value){
                // 根据key获取索引值 将数据插入到对应的位置(二维数组)
                var index = this.hashFunc(key,this.limit)
                // 根据索引值取出二维数组里对应位置的数组(三维数组)
                var bucket = this.storage[index]
                // 如果三维数组不存在也就是当时二维数组的下标值对应的地方没有数组就创建一个数组
                if(bucket === undefined){
                    bucket = []
                    this.storage[index] = bucket
                }
                // 通过线性查找三维数组判断是新增还是修改这里的值如果三维数组里有已经有值了就是修改
                for (let index = 0; index < bucket.length; index++) {
                    var tuple = bucket[index]
                    // 通过对比每个四维数组的key 跟传入的key是否相等判断为修改并进行value值的修改
                    if (tuple[0]===key){
                        tuple[1] = value
                        return
                    }
                }

                // 添加操作 向对应的三维数组里添加四维数组
                bucket.push([key,value])
                this.count += 1
                // 如果填充因子大于0.75就对一维数组进行扩容也就是limit
                if(this.count > this.limit*0.75){
                    var primeNum = this.getPrime(this.limit*2)
                    return this.resize(primeNum)
                }
            }

            // 获取存放的数据
            HashTable.prototype.get = function (key) {
                // 获取key对应的index
                var index = this.hashFunc(key, this.limit)
                // 获取对应的bucket
                var bucket = this.storage[index]
                // 如果bucket为null说明这个位置没有数据
                if(bucket === null){
                    return null
                }
                // 有bucket,判断是否有对应的key
                for (let i = 0; i < bucket.length; i++) {
                    const tuple = bucket[i];
                    // 三维数组里存放的的是两个数组 第一个存放的是key 第二个存放的value
                    if (tuple[0] === key){
                        return tuple[1]
                    }
                }
                // 没有找到
                return null
            }

            // 删除数据
            HashTable.prototype.remove = function (key){
                // 通过key获取对应的index
                var index = this.hashFunc(key,this.limit)
                // 获取一维数组对应的bucket(二维数组---坑位)
                var bucket  =this.storage[index]
                // 判断坑位是否有数组
                if(bucket === null){
                    return null
                }
                // 遍历bucket, 寻找对应坑位里对应的三维数组
                for (let i = 0; i < bucket.length; i++) {
                    var tuple = bucket[i];
                    // 三维数组里存放的的是两个数组(四维数组) 第一个存放的是key 第二个存放的value
                    if(tuple[0] === key){
                        bucket.splice(i,1)
                        this.count --
                        // 如果填充因子小于0.25就对一维数组进行缩容也就是limit减小
                        if(this.count < this.limit*0.25){
                            var primeNum = this.getPrime(Math.floor(this.limit/2))
                            this.resize(primeNum)
                        }
                        return tuple[1]
                    }
                }
                // 没有找到
                return null
            }

            // 判断数组是否为空
            HashTable.prototype.isEmpty = function (){
                return this.count === 0
            }

            // 获取哈希表的数据个数
            HashTable.prototype.size = function (){
                return this.count
            }

            // 哈希表扩容 当我们存入的数据跟坑位的比例大于0.75时需要对哈希表进行扩容来优化数据增删改查的速度
            HashTable.prototype.resize = function (newLimit) {
                // 因为对哈希表进行了扩容我们存入的数据的下标值就会发生改变(坑位发生改变) 我们需要保存旧的数据
                var oldStorage = this.storage 
                // 重置属性
                this.limit = newLimit
                this.count = 0
                this.storage = []
                // 遍历旧数组中所有的数据项,并重新插入到哈希表中
                oldStorage.forEach(function(backet) {
                    // 如果backet为null 说明这里面(坑位里)没有数据
                    if(backet === null ){
                        return
                    }
                    // backet里有数据,将里面的数据重新哈希化重新插入
                    for (let i = 0; i < backet.length; i++) {
                        const tuple = backet[i];
                        this.put(tuple[0],tuple[1])
                    }
                }.bind(this))
            }

            // 判断是否为质数 
            HashTable.prototype.isPrime = function (num){
                // 获取平方根 parseInt() 函数可解析一个字符串，并返回一个整数。
                var temp = parseInt(Math.sprt(num))
                // 循环判断 只能被自身以及1所整除数为质数  但是一般判断的时候我们循环除法到指定数的一半就行了  当指定数除以大于自身的数时时肯定不能整除的
                for (let i = 2; i < array.length; i++) {
                    if(num%i === 0){
                        return false
                    }
                }   
                return true
            }

            // 获取质数
            HashTable.prototype.getPrime = function (num) {
                while (!this.isPrime(num)){
                    num ++
                }
                return num
            }
        }

            // 测试代码
            // 1.创建哈希表
            var ht = new HashTable()
            
            // 2.插入数据
            ht.put("abc", "123")
            ht.put("cba", "321")
            ht.put("nba", "521")
            ht.put("mba", "520")
            
            // 3.获取数据
            alert(ht.get("abc"))
            ht.put("abc", "111")
            alert(ht.get("abc"))
            
            // 4.删除数据
            alert(ht.remove("abc"))
            alert(ht.get("abc"));
    </script>
    
</body>
</html>